package com.xcc.datastructure;

/**
 * @Description 【接雨水】练习
 *
 * 题目描述：
 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 * <p>
 * 示例 1：
 * 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
 * 输出：6
 * <p>
 * 示例 2：
 * 输入：height = [4,2,0,3,2,5]
 * 输出：9
 *
 * @Author xiechuang
 * @Date 2022/11/25
 */
public class TrapDemo {

    public static void main(String[] args) {

        // 预期结果：6
        int[] height1 = { 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 };
        System.out.println("v1：" + trapV1(height1));
        System.out.println("v2：" + trapV2(height1));

        // 预期结果：9
        int[] height2 = { 4, 2, 0, 3, 2, 5 };
        System.out.println("v1：" + trapV1(height2));
        System.out.println("v2：" + trapV2(height1));

        // 预期结果：1
        int[] height3 = { 4, 2, 3 };
        System.out.println("v1：" + trapV1(height3));
        System.out.println("v2：" + trapV2(height1));

        // 预期结果：26
        int[] height4 = { 0, 1, 2, 0, 3, 0, 1, 2, 0, 0, 4, 2, 1, 2, 5, 0, 1, 2, 0, 2 };
        System.out.println("v1：" + trapV1(height4));
        System.out.println("v2：" + trapV2(height1));

        // 预期结果：3
        int[] height5 = { 9, 6, 8, 8, 5, 6, 3 };
        System.out.println("v1：" + trapV1(height5));
        System.out.println("v2：" + trapV2(height1));

    }

    /**
     * 版本一
     * 思路：从第一个元素作为左侧边界开始进行遍历，找到右侧边界或者找到大于等于左侧边界的值，只用中间指针开始进行累加(中间指针初始为第二个元素，
     * 然后遍历到右侧边界的前一个元素，累加左右侧边界的小值减去当前指针的和，加完之后左侧边界更新为右侧边界继续遍历直到最后得出最终结果)
     *
     * @param height
     * @return
     */
    public static int trapV1(int[] height) {

        int length = height.length;
        int left = 0;
        int current = 1;
        int right = 2;
        int maxValue = 0;
        int result = 0;
        int index = 0;
        boolean flag = true;
        boolean loopFlag = true;

        if (length >= 3) {
            while(flag) {
                int leftValue = height[left];
                // 左侧边界值是否大于0
                if (leftValue > 0 && leftValue > height[left+1]) {
                    // 找到右侧边界大于等于左侧边界的值，如果找不到就找出右侧边界中的最大值
                    if (loopFlag) {
                        for (int i = 0; i < (length-left-2); i++) {
                            if (height[left] <= height[right]) {
                                maxValue = height[right];
                                index = right;
                                break;
                            }
                            if (height[right] >= maxValue) {
                                maxValue = height[right];
                                index = right;
                            }
                            right++;
                        }
                        loopFlag = false;
                    }

                    if (height[left+1] > maxValue) {
                        // 重置
                        left++;
                        current = left+1;
                        right = left + 2;
                        maxValue = 0;
                        loopFlag = true;
                    } else {
                        // 左右侧边界取小值
                        if (leftValue > maxValue) {
                            result += height[index] - height[current];
                        } else {
                            result += height[left] - height[current];
                        }
                        current++;
                        if (current == index) {
                            left = index;
                            current = left + 1;
                            right = left + 2;
                            maxValue = 0;
                            loopFlag = true;
                        }
                    }
                } else {
                    // 重置
                    left++;
                    current = left+1;
                    right = left + 2;
                    maxValue = 0;
                    loopFlag = true;
                }

                // 判断循环跳出条件
                if (left + 3 > length) {
                    flag = false;
                }

            }

        }

        return result;

    }

    /**
     * 版本二：动态规划
     * 思路：记录当前元素左侧的最大值和右侧的最大值，然后取交集，得出的值再减去当前元素进行累加得出结果
     *
     * @param height
     * @return
     */
    public static int trapV2(int[] height) {
        // 雨水数
        int result = 0 ;
        // 数组长度
        int length = height.length;

        if (length >= 3) {
            int currentLeftMax = 0;
            int currentRightMax = 0;
            int[] leftMax = new int[length];
            int[] rightMax = new int[length];
            // 遍历找到左右两侧的最大值
            for(int i = 0; i < length; i++) {
                currentLeftMax = Math.max(currentLeftMax, height[i]);
                leftMax[i] = currentLeftMax;
                currentRightMax = Math.max(currentRightMax, height[length - i - 1]);
                rightMax[length-i-1] = currentRightMax;
            }
            // 计算结果
            for (int k = 0; k < length; k++) {
                result += Math.min(leftMax[k], rightMax[k]) - height[k];
            }
        }

        return result;
    }

}
